import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IDEA
 * author:ju bai
 * Date:2021/1/30
 * Time:20:51
 **/
public class Main {

    public static void main(String[] args) {
        int i=0;
        Integer j = new Integer(0);
        System.out.println(i==j);
        System.out.println(j.equals(i));
    }

    public static void adjustDown2(int[] array,int parent,int len) {
        int child = 2*parent+1;
        while (child < len) {
            if(child+1 < len && array[child] < array[child+1]) {
                child++;//
            }
            if(array[child] > array[parent]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }
    //时间复杂度：nlogn
    public static void crateBigHeap2(int[] array) {
        for(int i = (array.length-1-1) /2; i>= 0;i--) {
            adjustDown2(array,i,array.length);
        }
    }

    /**
     * 时间复杂度：不管是最好，或者是最坏 O(n*logn)
     * 空间复杂度：O(1)
     * 稳定性：一会儿讨论
     * @param array
     */
    public static void heapSort2(int[] array) {
        crateBigHeap2(array);
        int end = array.length-1;
        while (end > 0) {
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            adjustDown2(array,0,end);
            end--;
        }
    }

    public static void main6(String[] args) {
        int[] array = { 27,15,19,18,28,34,65,49,25,37};
        heapSort2(array);
        System.out.println(Arrays.toString(array));
    }






    public static void main5(String[] args) {
        HeapDemo heapDemo = new HeapDemo();
        int[] array = { 27,15,19,18,28,34,65,49,25,37};
        System.out.println(Arrays.toString(array));
        heapDemo.createBigHeap(array);
        heapDemo.show();

        heapDemo.heapSort();
        heapDemo.show();

        /**
         * PriorityQueue  堆   优先级队列
         * PriorityQueue 底层 默认是一个小根堆
         * 每次存元素的时候  一定要保证 数据进入堆中后  依然可以维持为一个小堆/大堆
         * 每次取出一个元素的时候，一定要保证 剩下的元素 也要调整为一个小堆/大堆
         */
       /* PriorityQueue<Integer> qu = new PriorityQueue<>();
        qu.offer(10);
        qu.offer(100);
        qu.offer(3);
        qu.offer(40);
        qu.offer(6);
        System.out.println(qu.poll());//3
        System.out.println(qu.peek());*/
    }


    /**
     * 找前K个最大的元素
     * @param array
     */
    public static void topK(int[] array,int k) {

        //1、大小为K的小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1-o2;
            }
        });

        //2、遍历数组
        for (int i = 0; i < array.length; i++) {
            if(minHeap.size() < k) {
                minHeap.offer(array[i]);
            }else {
                Integer top = minHeap.peek();
                if(top != null) {
                    if (array[i] > top) {
                        minHeap.poll();
                        minHeap.offer(array[i]);
                    }
                }
            }
        }
        for (int i = 0; i < k; i++) {
            System.out.println(minHeap.poll());
        }
    }


    public static void main4(String[] args) {
        int[] array = { 27,15,19,18,28,34,65,49,25,37 };
        topK(array,3);
    }

    /**
     * 我们之前学过自定义比较器
     * @param args
     */
    public static void main3(String[] args) {
        //博哥：默认是小堆     我就要一个大堆呢
        PriorityQueue<Integer> qu = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                //o2 > o1   o1小于o2
                return o2-o1;
            }
        });
        //观察PriorityQueue的offer方法的实现方式 和我们讲的区别
        qu.offer(3);
        qu.offer(1);
        qu.offer(4);
        qu.offer(2);
        qu.offer(5);
        System.out.println(qu.poll());//1
        System.out.println(qu.poll());//2
        System.out.println(qu.poll());//3

    }

    public static void main2(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(10);
        queue.offer(65);
        queue.offer(5);
        queue.offer(76);
        queue.offer(24);
        System.out.println(queue.peek());
    }
    public static void main1(String[] args) {
        HeapDemo heapDemo = new HeapDemo();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        System.out.println(Arrays.toString(array));
        heapDemo.createBigHeap(array);
        heapDemo.show();
        heapDemo.push(100);
        heapDemo.show();

    }

}
